package datastructure.search;

/**
 * @author or2
 * @date 2021/7/22 21:59
 */
public class BinarySearch {

    /**
     * 对有序数字进行二分查找
     * @param arr 有序数字
     * @param key 要查找的关键字
     * @param <E> {@code E extends Comparable<E> }
     * @return 有则返回在数字中的下标<br/>无则返回 {@code -1 }
     */
    public static <E extends Comparable<E>> int search(E[] arr, E key) {

        int length = arr.length;
        int mid = length >> 1, lIndex = 0, rIndex = length - 1;

        while (lIndex <= rIndex) {

            if (arr[mid].compareTo(key) == 0) {
                return mid;
            }
            if (arr[mid].compareTo(key) > 0) {
                rIndex = mid - 1;
            } else {
                lIndex = mid + 1;
            }
            mid = lIndex + (rIndex - lIndex >> 1);
        }

        return -1;
    }
}
